package com.xieyong.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode3373 {
    public static void main(String[] args) {
        int[][] edge1 = new int[][]{{0, 1}, {0, 2}, {2, 3}, {2, 4}};
        int[][] edge2 = new int[][]{{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}};
        Leetcode3373 d = new Leetcode3373();
        int[] result = d.maxTargetNodes(edge1, edge2);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + "  ");
        }
    }
//    以下代码超时了一例
//    public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
//        int n = edges1.length + 1;
//        int[] count1 = build(edges1, 0);
//        int[] count2 = build(edges2, 1);
//        int maxCount2 = 0;
//        for (int c : count2) {
//            if (c > maxCount2) {
//                maxCount2 = c;
//            }
//        }
//        int[] res = new int[n];
//        for (int i = 0; i < n; i++) {
//            res[i] = count1[i] + maxCount2;
//        }
//        return res;
//    }
//
//    private int[] build(int[][] edges, int k) {
//        int n = edges.length + 1;
//        List<List<Integer>> children = new ArrayList<>();
//        for (int i = 0; i < n; i++) {
//            children.add(new ArrayList<>());
//        }
//        for (int[] edge : edges) {
//            children.get(edge[0]).add(edge[1]);
//            children.get(edge[1]).add(edge[0]);
//        }
//        int[] res = new int[n];
//        List<Integer> noparent = new ArrayList<>();
//        noparent.add(-1);
//        for (int i = 0; i < n; i++) {
//            if(k == 0) {
//                res[i] = dfs(i, noparent, children);
//            } else {
//                List<Integer> childlist = children.get(i);
//                for(int child : childlist) {
//                    res[i] = dfs(child, noparent, children);
//                }
//            }
//        }
//        return res;
//    }
//
//    private int dfs(int node, List<Integer> parents, List<List<Integer>> children) {
//        int res = 1;
//        List<Integer> list = children.get(node);
//        List<Integer> list2 = new ArrayList<>();
//        for (Integer child : list) {
//            if(parents.contains(child)) {
//                continue;
//            }
//            for (int child2 : children.get(child)) {
//                if(!parents.contains(child2) && child2 != child && child2 != node) {
//                    list2.add(child2);
//                }
//            }
//        }
//        for (int child2 : list2) {
//            res += dfs(child2, list, children);
//        }
//        return res;
//    }

    public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
        int n = edges1.length + 1, m = edges2.length + 1;
        int[] color1 = new int[n];
        int[] color2 = new int[m];
        int[] count1 = build(edges1, color1);
        int[] count2 = build(edges2, color2);
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = count1[color1[i]] + Math.max(count2[0], count2[1]);
        }
        return res;
    }

    private int[] build(int[][] edges, int[] color) {
        int n = edges.length + 1;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            children.get(edge[0]).add(edge[1]);
            children.get(edge[1]).add(edge[0]);
        }
        int res = dfs(0, -1, 0, children, color);
        return new int[]{res, n - res};
    }

    private int dfs(int node, int parent, int depth, List<List<Integer>> children, int[] color) {
        int res = 1 - depth % 2;
        color[node] = depth % 2;
        for (int child : children.get(node)) {
            if (child == parent) {
                continue;
            }
            res += dfs(child, node, depth + 1, children, color);
        }
        return res;
    }
}
